#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            int max = 0;
            for (auto& num : nums) {
                if (num > max) {
                    max = num;
                }
            }
            return max;
        }
        vector<int> dp1(n + 1);
        vector<int> dp2(n);

        for (int i = n - 1; i >= 1; i--) {
            dp1[i] = max(dp1[i + 1], nums[i] + dp1[min(n, i + 2)]);
        }

        for (int i = n - 2; i >= 0; i--) {
            dp2[i] = max(dp2[i + 1], nums[i] + dp2[min(n - 1, i + 2)]);
        }

        return dp1[1] > dp2[0] ? dp1[1] : dp2[0];
    }
};